# 作者: 赵炳森
# 2025年11月06日14时26分10秒
# 2215031808@qq.com
import random
import time
import sys
sys.setrecursionlimit(100000)
class Sort:
    def __init__(self, n):
        self.len=n
        # self.arr=[3,87,2,93,78,56,61,38,12,40]
        self.arr=[0]*n
        self.random_data()
    def random_data(self):
        for i in range(self.len):
            self.arr[i]=random.randint(0,99)
    def quick_sort(self,left,right):
        if left<right:
            pivot=self.partition(left,right)
            self.quick_sort(left,pivot-1)
            self.quick_sort(pivot+1,right)
    def partition(self,left,right):
        arr=self.arr
        k=i=left
        random_pos=random.randint(left,right)
        arr[random_pos],arr[right]=arr[right],arr[random_pos]
        for i in range(left,right):
            if arr[i]<arr[right]:
                arr[i],arr[k]=arr[k],arr[i]
                k+=1
        arr[k],arr[right]=arr[right],arr[k]
        return k
    def adjust_max_heap(self,pos,arr_len):
        arr=self.arr
        dad=pos
        son=2*pos+1
        while son<arr_len:
            if son+1<arr_len and arr[son]<arr[son+1]:
                son+=1
            if arr[son]>arr[dad]:
                arr[dad],arr[son]=arr[son],arr[dad]
                dad=son
                son=2*dad+1
            else:
                break

    def heap_sort(self):
        for parent in range(self.len//2-1,-1,-1):
            self.adjust_max_heap(parent,self.len)
        arr=self.arr
        arr[0],arr[self.len-1]=arr[self.len-1],arr[0]
        for arr_len in range(self.len-1,1,-1):
            self.adjust_max_heap(0,arr_len)
            arr[0],arr[arr_len-1]=arr[arr_len-1],arr[0]

    def test_time_use(self,sort_func,*args,**kwargs):
        start = time.time()
        sort_func(*args,**kwargs)
        end = time.time()
        print(f'总计用时{end-start}')

if __name__=='__main__':
    count=100000
    my_sort=Sort(count)
    # print(my_sort.arr)
    # my_sort.quick_sort(0,count-1)
    my_sort.test_time_use(my_sort.heap_sort)
    # my_sort.heap_sort()
    # print(f'总计用时{end-start}')
    # print(my_sort.arr)